public class Num1653 {
    //给你一个字符串s，它仅包含字符'a' 和'b' 。
    //你可以删除s中任意数目的字符，使得s 平衡。当不存在下标对(i,j)满足i < j ，且s[i] = 'b' 的同时s[j]= 'a' ，此时认为 s 是 平衡 的。
    //请你返回使 s平衡的 最少删除次数
    public int minimumDeletions(String s) {
        //1.前后缀分解
//        int del = 0;
//        char[] chars = s.toCharArray();
//        for (char c : chars) {
//            if (c == 'a') del++;
//        }
//        int ans = del;
//        for (char c : chars) {
//            del += (c - 'a') * 2 - 1; //遇到'a'减少删除次数，遇到'b'增加删除次数
//            ans = Math.min(ans,del);//找出最小删除次数
//        }
//        return ans;
        //方法二动态规划
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] arr = new int[n];
        int countB = 0;
        for (int i = 0; i < n; i++) {
            if (chars[i] == 'b') {
                countB++;
                if (i - 1 >= 0) arr[i] = arr[i - 1];
            }else {
                //删除'a'，则删除次数为f(n - 1) + 1
                //不删除'a'，则删除次数为del('b')
                if (i > 0) {
                    arr[i] = Math.min(arr[i - 1] + 1,countB);
                }
            }
        }
        return arr[n - 1];
    }
}
